package Stack;

import java.util.Arrays;

public class _853_CarFleet {
    //solution 1:use iterative:wrong answer:what if there are more than 2 car at the same time meet in the road
    //can use a matrix to imply,but it might be over time limited
    public int carFleet_w(int target, int[] position, int[] speed) {
        int count = 0;
        for (int i = 0; i < position.length; i++) {
            for (int j = i + 1; j < position.length; j++) {
                int pos1 = position[i], pos2 = position[j];
                while (pos1 < target && pos2 < target) {
                    pos1 += speed[i];
                    pos2 += speed[j];
                    if (pos1 == pos2 ) {
                        count++;
                    }
                }
            }
        }
        return count+(speed.length-count*2);
    }

    //special case:if one car fleet more than 1 car,just count 1 as the question seens.
    public int carFleet(int target, int[] position, int[] speed) {
        int N = position.length;
        Car[] cars = new Car[N];
        for (int i = 0; i < N; i++) {
            cars[i] = new Car(position[i], (double) (target - position[i] )/ speed[i]);
        }
        Arrays.sort(cars, (a, b) -> Integer.compare(a.position, b.position));
        int res = 0,t = N;
        while (--t > 0) {
            if (cars[t].time < cars[t - 1].time) {
                res++;
            } else {
                cars[t - 1] = cars[t];
            }
        }
        return res + (t == 0 ? 1 : 0);
    }

    class Car{
        int position;
        double time;

        Car(int p, double time) {
            this.position = p;
            this.time = time;
        }
    }
}
